package main

import "fmt"

// 定义链表节点
type ListNode struct {
	Val  int
	Next *ListNode
}

// 合并两个有序链表
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	// 创建一个哑节点，简化代码逻辑
	dummy := &ListNode{}
	curr := dummy

	// 遍历两个链表，将值较小的节点接在结果链表后面
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			curr.Next = l1
			l1 = l1.Next
		} else {
			curr.Next = l2
			l2 = l2.Next
		}
		curr = curr.Next
	}

	// 将剩余的节点接在结果链表后面
	if l1 != nil {
		curr.Next = l1
	} else {
		curr.Next = l2
	}

	// 返回结果链表的头节点
	return dummy.Next
}

// 合并k个有序链表
func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}

	// 递归地将链表数组两两合并
	for len(lists) > 1 {
		nextLists := []*ListNode{}
		for i := 0; i < len(lists); i += 2 {
			if i+1 < len(lists) {
				nextLists = append(nextLists, mergeTwoLists(lists[i], lists[i+1]))
			} else {
				nextLists = append(nextLists, lists[i])
			}
		}
		lists = nextLists
	}

	return lists[0]
}

// 打印链表
func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d", head.Val)
		if head.Next != nil {
			fmt.Printf(" -> ")
		}
		head = head.Next
	}
	fmt.Println("")
}

func main() {
	// 创建n个有序链表
	lists := []*ListNode{
		&ListNode{Val: 1, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}},
		&ListNode{Val: 1, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4}}},
		&ListNode{Val: 2, Next: &ListNode{Val: 6}},
	}

	// 合并n个有序链表
	mergedList := mergeKLists(lists)

	// 打印合并后的链表
	fmt.Println("合并后的链表:")
	printList(mergedList)
}
